๋ฌธ์
๊ทธ๋ํ๋ฅผ DFS๋ก ํ์ํ ๊ฒฐ๊ณผ์ BFS๋ก ํ์ํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋จ, ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ ์ด ์ฌ๋ฌ ๊ฐ์ธ ๊ฒฝ์ฐ์๋ ์ ์ ๋ฒํธ๊ฐ ์์ ๊ฒ์ ๋จผ์ ๋ฐฉ๋ฌธํ๊ณ , ๋ ์ด์ ๋ฐฉ๋ฌธํ ์ ์๋ ์ ์ด ์๋ ๊ฒฝ์ฐ ์ข ๋ฃํ๋ค. ์ ์ ๋ฒํธ๋ 1๋ฒ๋ถํฐ N๋ฒ๊น์ง์ด๋ค.
์ ๋ ฅ
- ์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ N(1 โค N โค 1,000), ๊ฐ์ ์ ๊ฐ์ M(1 โค M โค 10,000), ํ์์ ์์ํ ์ ์ ์ ๋ฒํธ V๊ฐ ์ฃผ์ด์ง๋ค. ๋ค์ M๊ฐ์ ์ค์๋ ๊ฐ์ ์ด ์ฐ๊ฒฐํ๋ ๋ ์ ์ ์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ค ๋ ์ ์ ์ฌ์ด์ ์ฌ๋ฌ ๊ฐ์ ๊ฐ์ ์ด ์์ ์ ์๋ค. ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๊ฐ์ ์ ์๋ฐฉํฅ์ด๋ค.
์ถ๋ ฅ
- ์ฒซ์งธ ์ค์ DFS๋ฅผ ์ํํ ๊ฒฐ๊ณผ๋ฅผ, ๊ทธ ๋ค์ ์ค์๋ BFS๋ฅผ ์ํํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ค. V๋ถํฐ ๋ฐฉ๋ฌธ๋ ์ ์ ์์๋๋ก ์ถ๋ ฅํ๋ฉด ๋๋ค.
๐ Logic
class Graph {
public ArrayList<ArrayList<Integer>> graph;
public boolean[] visited = new boolean[1001];
public StringBuilder path = new StringBuilder();
}
- graph๋ฅผ ์ ์ฅํ๊ธฐ ์ํ ๋์ 2์ฐจ์ ๋ฐฐ์ด
- ์ ์ ์ ๋ํ ๋ฐฉ๋ฌธ ์ฌ๋ถ ์ ์ฅ์ ์ํ
boolean๋ฐฐ์ด DFS์BFS์ ๋ฐฉ๋ฌธ ์์๋ฅผ ์ ์ฅํ๋stringBuilder
public void dfs(int start) {
if (!visited[start]) {
path.append(start);
path.append(" ");
visited[start] = true;
for (int i = 0; i < graph.get(start).size(); i++) {
if (!visited[graph.get(start).get(i)]) {
this.dfs(graph.get(start).get(i));
}
}
}
}
- ์ฌ๊ท ํธ์ถ์ ์ด์ฉํ DFS ๊ตฌํ
public void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
path.append("\n");
path.append(start);
while (!q.isEmpty()) {
int cur = q.poll();
for (int i = 0; i < graph.get(cur).size(); i++) {
if (!visited[graph.get(cur).get(i)]) {
visited[graph.get(cur).get(i)] = true;
path.append(" ");
path.append(graph.get(cur).get(i));
q.offer(graph.get(cur).get(i));
}
}
}
}
- Queue๋ฅผ ์ด์ฉํ BFS ๊ตฌํ
for (int i = 1; i <= n; i++) {
Collections.sort(g.graph.get(i));
}
- ๋ฒํธ๊ฐ ๋ฎ์ ์ ์ ๋ถํฐ ๋ฐฉ๋ฌธํ๋ผ๋ ๋ฌธ์ ์ ์กฐ๊ฑด์ ์ํ ์ ๋ ฌ
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Graph {
public ArrayList<ArrayList<Integer>> graph;
public boolean[] visited = new boolean[1001];
public StringBuilder path = new StringBuilder();
public Graph(int size) {
this.graph = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < size + 1; i++) {
graph.add(new ArrayList<Integer>());
}
}
public void DoubleAdd(int x, int y) {
graph.get(x).add(y);
graph.get(y).add(x);
}
public void dfs(int start) {
if (!visited[start]) {
path.append(start);
path.append(" ");
visited[start] = true;
for (int i = 0; i < graph.get(start).size(); i++) {
if (!visited[graph.get(start).get(i)]) {
this.dfs(graph.get(start).get(i));
}
}
}
}
public void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
path.append("\n");
path.append(start);
while (!q.isEmpty()) {
int cur = q.poll();
for (int i = 0; i < graph.get(cur).size(); i++) {
if (!visited[graph.get(cur).get(i)]) {
visited[graph.get(cur).get(i)] = true;
path.append(" ");
path.append(graph.get(cur).get(i));
q.offer(graph.get(cur).get(i));
}
}
}
}
public StringBuilder getPath() {
return path;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int start = sc.nextInt();
Graph g = new Graph(n);
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
g.DoubleAdd(a,b);
}
for (int i = 1; i <= n; i++) {
Collections.sort(g.graph.get(i));
}
Arrays.fill(g.visited,false);
g.dfs(start);
Arrays.fill(g.visited,false);
g.bfs(start);
System.out.print(g.getPath().toString());
sc.close();
}
}
โ๏ธ Review
- ์ฑ๊ณตํ์๋ค๊ฐ ์คํจ๋ก ์ฌ์ฑ์ ๋์ด ์ด๋ฒ ๊ธฐํ์
JAVA๋ก ๋ณํํ๋ฉด์ ๋ค์ ํผ ๋ฌธ์ class Graph์ ๊ฐ์ด ํด๋์ค๋ฅผ ๋ง๋๋ ๋ฐฉ์์ ์ด์ฉํด Graph์ ๊ด๋ จ๋ ์ฒ๋ฆฌ๋ค์ ์ต๋ํ ํด๋์ค ๋ด๋ถ์์ ๊ตฌํํ๋๋ก ํ๋ค.-
์ฒ์์๋
int[] path๋ฅผ ๋ ๋ฒ ์ฌ์ฉํ์ฌDFS์ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๊ณ ,BFS์ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ๋ฐฉ์์ผ๋ก ๊ตฌํํ์๋๋ฐ, ๋ค๋ฅธ ๋ฐฉ์์ ์ฐพ์๋ณด๋ค๊ฐStringBuilderํด๋์ค๋ผ๋ ๊ฒ์ ๋ฐ๊ฒฌํ์ฌ ์ด๋ฅผ ์ฌ์ฉํด๋ณด์๋ค.StringBuilder: ์ฌ๋ฌ ๋ฌธ์์ด์ ๋ถ์ด๋ ์ฐ์ฐ์ ์ํํ๋ ๊ฒฝ์ฐ ํจ์จ์ ์ธ ํด๋์ค๋ก, ํด๋น ๋ฌธ์ ์์๋ ์ ์ ์ ๋ฐฉ๋ฌธ ์์๋ฅผ ์์ฐจ์ ์ผ๋ก ์ ์ฅํ๊ธฐ ์ํด ์ฌ์ฉํ๋ค.
- ๊ตฌํ ๋ฐฉ์์ ํ๋ฆฐ ๊ฒ์ด ์์ด๋ณด์๋๋ฐ ์๊พธ ํ๋ ธ์ต๋๋ค ๊ฐ ๋ ์ ํ๊ฐ ๋ ๋ ์ฆ์ ๋ฐ๊ฒฌํ ํ ๋ฐ๋ก๋ก ๋๋ฒ๊น ์ ํด๋ณด๋, ์ ๋ ฌ ์ ๋ฐ๋ณต ํ์๊ฐ 1๋ฒ ๋ชจ์๋ ๊ฒ์ด์๋ค.
- ์ถ๊ฐ๋ก,
visited๋ฐฐ์ด์int๋ก ํ ๊ฒฝ์ฐ์boolean์ผ๋ก ํ ๊ฒฝ์ฐ ์๊ฐ๊ณผ ๋ฉ๋ชจ๋ฆฌ ์ฐจ์ด๊ฐ ์กด์ฌํ๋๋ฐ,boolean์ ๋ฉ๋ชจ๋ฆฌ๊ฐ ๋ ์ ๊ณ ์๊ฐ์ด ๊ฐ์ํ์๊ฑฐ๋ ์์๊ณผ๋ ๋ฌ๋ฆฌ, ๋ฉ๋ชจ๋ฆฌ๊ฐ ์ฆ๊ฐํ ๊ฒ์ ํ์ธํ๋ค. ์์ง ์ด์ ๋ ์ ๋ชจ๋ฅด๊ฒ ๋ค ..